<!DOCTYPE html>
<html>

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <link rel="stylesheet" href="css/prism.css">
  <style>
    html,
    body {
      box-sizing: border-box;
      margin: 0;
      padding: 0;
      height: 100%;
      font-size: 12px;
    }

    body {
      min-height: 500px;
    }

    section {
      display: flex;
      flex-wrap: wrap;
    }

    .code {
      margin-top: 3px;
    }

    pre[class*=language-] {
      margin: 0;
      padding: 0;
    }

    main {
      border-top: 2px solid #ccc;
      width: 100%;
      height: 65%;
      min-height: 200px;
    }
  </style>
  <title>Leetcode 2 - 链表相加</title>
</head>

<body>
  <section class="frames"></section>
  <section style="display: none;">
    <pre><code class="language-java">int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}</code></pre>
  </section>
  <main></main>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>链表1&nbsp;</span><input type="text" value="2,4,3" id='l1' class="saveable array">
    <span>链表2&nbsp;</span><input type="text" value="5,6,4" id='l2' class="saveable array">
    <input type="button" value="case1" onclick="onCase1()">
    <input type="button" value="case2" onclick="onCase2()">
  </div>
  <div style='margin: 2px 2px 0 0; padding: 4px 6px;'>
    <span>动画速度(ms)&nbsp;</span><input type="number" step="100" value="300" id="animate_speed" class="saveable int"
      style="width: 40px;">
    <span>矩形宽</span><input type="number" step="1" value="60" id="RECT_WIDTH" class="saveable int" style="width: 40px;">
    <span>矩形高</span><input type="number" step="1" value="20" id="RECT_HEIGHT" class="saveable int" style="width: 40px;">
    <span>间隙</span><input type="number" step="1" value="40" id="SPACE" class="saveable int" style="width: 40px;">
    <input style='font-size:12px;' type="button" value="保存" onclick="onSave('leetcode_2')">
  </div>
  <script src="js/p5.js"></script>
  <script src="js/p5-svg.js"></script>
  <script src="js/util.js"></script>
  <script src="js/prism.js"></script>
  <script>
    function onCase1() {
      document.getElementById("l1").value = "2,4,3"
      document.getElementById("l2").value = "5,6,4"
      onSave('leetcode_2')
    }
    function onCase2() {
      document.getElementById("l1").value = "9,9,9,9,9,9,9"
      document.getElementById("l2").value = "9,9,9,9"
      onSave('leetcode_2')
    }
    class ListNode {
      constructor(val) {
        this.val = val
        this.next = null
        this.size = 0
        this.carry = 0
        this.p1i = 0
        this.p2i = 0
        this.pi = 0
      }
      static of(values) {
        const sentinel = new ListNode(-1)
        let p = sentinel
        for (let v of values) {
          p.next = new ListNode(v)
          sentinel.size++
          p = p.next
        }
        if (sentinel.next != null) {
          sentinel.next.size = sentinel.size
        }
        return sentinel.next
      }
      static copy(list) {
        let p = list
        const sentinel = new ListNode(-1)
        let r = sentinel
        while (p != null) {
          r.next = new ListNode(p.val)
          r = r.next
          p = p.next
        }
        if (sentinel.next != null) {
          sentinel.next.size = list.size
          sentinel.next.carry = list.carry
          sentinel.next.last = list.last
          sentinel.next.p1i = list.p1i
          sentinel.next.p2i = list.p2i
          sentinel.next.pi = list.pi
        }
        return sentinel.next
      }
    }
    const options = loadOptionsFromStorage('leetcode_2')
    const d = new Draw(options.animate_speed)
    const RECT_WIDTH = options.RECT_WIDTH
    const RECT_HEIGHT = options.RECT_HEIGHT
    const SPACE = options.SPACE
    const l1 = ListNode.of(options.l1)
    const l2 = ListNode.of(options.l2)

    function addTwoNumbers(p1, p2) {
      const sentinel = new ListNode(-1)
      let p = sentinel
      while (p1 != null && p2 != null) {
        let sum = p1.val + p2.val + sentinel.carry
        d.add({ cloned: ListNode.copy(sentinel) }, frame)
        if (sum >= 10) {
          sentinel.carry = 1
          sum -= 10
        } else {
          sentinel.carry = 0
        }
        p.next = new ListNode(sum)
        sentinel.size++
        p = p.next
        p1 = p1.next
        p2 = p2.next
        sentinel.p1i++
        sentinel.p2i++
        sentinel.pi++
      }
      if (p1 != null) {
        while (p1 != null) {
          let sum = p1.val + sentinel.carry
          d.add({ cloned: ListNode.copy(sentinel) }, frame)
          if (sum >= 10) {
            sentinel.carry = 1
            sum -= 10
          } else {
            sentinel.carry = 0
          }
          p.next = new ListNode(sum)
          sentinel.size++
          p = p.next
          p1 = p1.next
          sentinel.p1i++
          sentinel.pi++
        }
      }
      if (p2 != null) {
        while (p2 != null) {
          let sum = p2.val + sentinel.carry
          d.add({ cloned: ListNode.copy(sentinel) }, frame)
          if (sum >= 10) {
            sentinel.carry = 1
            sum -= 10
          } else {
            sentinel.carry = 0
          }
          p.next = new ListNode(sum)
          sentinel.size++
          p = p.next
          p2 = p2.next
          sentinel.p2i++
          sentinel.pi++
        }
      }

      if (sentinel.carry == 1) {
        d.add({ cloned: ListNode.copy(sentinel) }, frame)
        p.next = new ListNode(sentinel.carry)
        sentinel.size++
      }
      if (sentinel.next != null) {
        sentinel.next.size = sentinel.size
      }
      sentinel.last = true
      d.add({ cloned: ListNode.copy(sentinel) }, frame)
      return sentinel.next
    }
    let list
    function setup() {
      const WIN_WIDTH = document.querySelector('main').clientWidth
      const WIN_HEIGHT = document.querySelector('main').clientHeight
      const FONT_SIZE = 16
      createCanvas(WIN_WIDTH, WIN_HEIGHT, SVG)
      textSize(FONT_SIZE)
      textAlign(CENTER)
      list = addTwoNumbers(l1, l2)
      d.updateFrameButtons()
    }
    function draw() {
      d.draw(() => background('#eee'), () => true)
    }
    function frame({ cloned: sentinel }) {
      if (sentinel) {
        const startX = width / 2 - 200
        const startY = 100
        let p1 = l1
        let p2 = l2
        let p = sentinel
        let x = startX
        let y = startY
        // console.log(sentinel.p1i, sentinel.p2i, sentinel.pi)
        for (let i = 0; i < list.size + 1; i++) {
          if (p1 != null) {
            rect(x, y, RECT_WIDTH, RECT_HEIGHT)
            text(p1.val, x + RECT_WIDTH / 2, y + RECT_HEIGHT / 2 + 5)
          }
          if (i == sentinel.p1i) {
            text("p1", x + RECT_WIDTH / 2, y - RECT_HEIGHT / 2 + 4)
          }

          if (p2 != null) {
            rect(x, y + RECT_HEIGHT + SPACE, RECT_WIDTH, RECT_HEIGHT)
            text(p2.val, x + RECT_WIDTH / 2, y + RECT_HEIGHT / 2 + 5 + RECT_HEIGHT + SPACE)
          }
          if (i == sentinel.p2i) {
            text("p2", x + RECT_WIDTH / 2, y - RECT_HEIGHT / 2 + 4 + RECT_HEIGHT + SPACE)
          }

          if (p != null) {
            rect(x - RECT_WIDTH, y + (RECT_HEIGHT + SPACE) * 2, RECT_WIDTH, RECT_HEIGHT)
            text(p.val, x + RECT_WIDTH / 2 - RECT_WIDTH, y + RECT_HEIGHT / 2 + 5 + (RECT_HEIGHT + SPACE) * 2)
          }
          if (i == sentinel.pi) {
            text("p", x - RECT_WIDTH / 2, y + RECT_HEIGHT * 1.5 + 5 + (RECT_HEIGHT + SPACE) * 2)
          }
          if (p1 != null) p1 = p1.next
          if (p2 != null) p2 = p2.next
          if (p != null) p = p.next
          x += RECT_WIDTH
        }
        if (!sentinel.last) {
          x = startX + sentinel.size * RECT_WIDTH + RECT_WIDTH / 2
          y = y + (RECT_HEIGHT + SPACE) * 2 - RECT_HEIGHT * 0.5
          circle(x, y, 20)
          text(sentinel.carry, x, y + 5)
        }
      }
    }

  </script>
</body>

</html>